package Leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class problem102 {

    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        LinkedList<TreeNode> aList = new LinkedList<>();
        LinkedList<TreeNode> oList = new LinkedList<>();
        List<List<Integer>> list = new ArrayList<>();

        if(root==null){
            return list;
        }

        List<Integer> tempList ;


        aList.add(root);

        while(aList.size()!=0 || oList.size() != 0){
            tempList = new ArrayList<>();
            while(aList.size()!=0){
                if(aList.peek().left!=null){
                    oList.add(aList.peek().left);
                }
                if(aList.peek().right!=null){
                    oList.add(aList.peek().right);
                }
                tempList.add(aList.poll().val);
            }
            if(tempList.size()!=0){
                list.add(tempList);
            }

            tempList = new ArrayList<>();
            while(oList.size()!=0){
                if(oList.peek().left!=null){
                    aList.add(oList.peek().left);
                }
                if(oList.peek().right!=null){
                    aList.add(oList.peek().right);
                }
                tempList.add(oList.poll().val);
            }
            if(tempList.size()!=0){
                list.add(tempList);
            }
        }
        return list;

    }
}
